Euler Problem 15

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?



In [1]:

    
def binomial(n,r):
    if r<0 or r>n:
        return 0
    if r > n//2:
        r = n - r
    b = 1
    for i in range(r):
        b = (b * (n-i)) // (i + 1)
    return b

print(binomial(40,20))

137846528820

Explanation: Each route has 20 downward segments and 20 rightward segments. The number of routes is equal to the binomial coefficient $$\binom{40}{20} = \frac{40!}{20!\,20!} = 137846528820$$ because the routes can be constructed by choosing 20 out of the 40 segments to be downward.